#include <bits/stdc++.h>
using namespace std;

/*
2799. 统计完全子数组的数目
已解答
中等
相关标签
相关企业
提示
给你一个由 正 整数组成的数组 nums 。

如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：

子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。

子数组 是数组中的一个连续非空序列。

 

示例 1：

输入：nums = [1,3,1,2,2]
输出：4
解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
示例 2：

输入：nums = [5,5,5,5]
输出：10
解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。
 

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2000
*/

// 法一
class Solution {
	public:
	int countCompleteSubarrays(vector<int>& nums) {
		// 获取数组中不同元素的数目
		unordered_set<int> unique_elements(nums.begin(), nums.end());
		int total_unique = unique_elements.size();

		int left = 0, right = 0, n = nums.size();
		int count = 0;
		unordered_map<int, int> freq_map;
		// 滑动窗口
		while (right < n) {
			// 将右指针指向的元素加入窗口
			freq_map[nums[right]]++;
			// 检查窗口内不同元素的数量
			while (freq_map.size() == total_unique) {
				// 如果窗口内的不同元素数量等于总的不同元素数量，
				// 那么从左侧开始缩小窗口，所有右侧子数组都是满足条件的
				count += (n - right);
				// 缩小窗口
				freq_map[nums[left]]--;
				if (freq_map[nums[left]] == 0) {
					freq_map.erase(nums[left]);
				}
				left++;
			}
			// 向右扩展窗口
			right++;
		}
		return count;
	}
};

// 法二
class Solution {
	public:
	int countCompleteSubarrays(vector<int>& nums) {
		// cnt 数组用来记录每个数字出现的次数。最大值为 2001，假设数字范围是 [1,
		// 2000]
		int cnt[2001];
		int l = nums.size();         // 获取数组的长度
		int sz = 0;                  // 记录数组中不同元素的数量
		memset(cnt, 0, sizeof(cnt)); // 将 cnt 数组初始化为 0
		// 第一遍遍历，统计 nums 中不同元素的数量
		for (int i = 0; i < l; i++) {
			cnt[nums[i]]++; // 记录每个元素出现的次数
			if (cnt[nums[i]] == 1) {
				sz++; // 如果该元素是第一次出现，增加不同元素数量
			}
		}
		// 清空 cnt 数组，为第二次遍历准备
		memset(cnt, 0, sizeof(cnt));
		int ans = 0; // 用来记录完全子数组的数量
		// 第二次遍历，使用滑动窗口法来查找所有符合条件的子数组
		for (int i = 0, j = 0; i < l; i++) {
			cnt[nums[i]]++; // 进入窗口时，增加当前元素的计数
			if (cnt[nums[i]] == 1) {
				sz--; // 如果当前元素是第一次加入窗口，减少 sz（不同元素的数量）
			}
			// 当窗口内的不同元素数量等于整个数组中的不同元素数量时，开始统计
			while (!sz) {
				while (j < l && !sz) {
					// 对每个符合条件的窗口，向右扩展 j（相当于移动左指针）
					cnt[nums[j]]--; // 移出元素 nums[j]，减少其计数
					ans += (l - i); // 每次移出元素后，都会形成若干个符合条件的子数组，数量为
									// (l - i)
					if (cnt[nums[j++]] == 0) {
						sz++; // 如果移除该元素后，窗口内没有该元素了，恢复
							  // sz（表示不同元素的数量）
					}
				}
			}
		}
		return ans; // 返回找到的完全子数组的数量
	}
};

